package com.skh.array;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * 数组形式的整数加法
 */
public class AddToArrayForm {
    /**
     * 对于非负整数 X 而言，X 的数组形式是每位数字按从左到右的顺序形成的数组。例如，如果 X = 1231，那么其数组形式为 [1,2,3,1]。
     * <p>
     * 给定非负整数 X 的数组形式 A，返回整数 X+K 的数组形式。
     * <p>
     *  
     * <p>
     * 示例 1：
     * <p>
     * 输入：A = [1,2,0,0], K = 34
     * 输出：[1,2,3,4]
     * 解释：1200 + 34 = 1234
     * 示例 2：
     * <p>
     * 输入：A = [2,7,4], K = 181
     * 输出：[4,5,5]
     * 解释：274 + 181 = 455
     * 示例 3：
     * <p>
     * 输入：A = [2,1,5], K = 806
     * 输出：[1,0,2,1]
     * 解释：215 + 806 = 1021
     * 示例 4：
     * <p>
     * 输入：A = [9,9,9,9,9,9,9,9,9,9], K = 1
     * 输出：[1,0,0,0,0,0,0,0,0,0,0]
     * 解释：9999999999 + 1 = 10000000000
     */

    public static List<Integer> addToArrayForm(int[] A, int K) {

        /**
         * 思路
         * 让我们逐位将数字加在一起。举一个例子，如果要计算 123123 与 912912 的和。我们顺次计算 3+23+2、2+12+1、1+91+9。任何时候，当加法的结果大于等于 1010，我们要将进位的 11 加入下一位的计算中去，所以最终结果等于 10351035。
         * 算法
         * 我们可以对以上的想法做一个小变化，让它实现起来更容易 —— 我们将整个加数加入数组表示的数的最低位。
         * 继续之前的例子 123+912123+912，我们把它表示成 [1, 2, 3+912][1,2,3+912]。然后，我们计算 3+912 = 9153+912=915。55 留在当前这一位，将 910/10=91910/10=91 以进位的形式加入下一位。
         * 然后，我们再重复这个过程，计算 [1, 2+91, 5][1,2+91,5]。我们得到 9393，33 留在当前位，将 90/10=990/10=9 以进位的形式加入下一位。继而又得到 [1+9, 3, 5][1+9,3,5]，重复这个过程之后，最终得到结果 [1, 0, 3, 5][1,0,3,5]。
         */
        List<Integer> result = new ArrayList<>();
        int cur = K;
        int i = A.length-1;

        while (cur > 0||i>=0) {
            if (i >= 0) {
                cur = A[i] + cur;
                i--;
            }
            result.add(cur % 10);
            cur = cur / 10;
        }


        //翻转集合
        Collections.reverse(result);


        return result;
    }

    public static void main(String[] args) {
        int[] A = {2, 7, 4};
        List<Integer> integers = AddToArrayForm.addToArrayForm(A, 181);
        System.out.println("integers = " + integers);
    }
}
